package Sort_work;

import java.util.Arrays;

/**
 * 插入排序
 * 思想：设i、j
 *      用i来遍历数组 通过j遍历0 - i-1 的数组元素，对数组进行排序
 *      当i走到数组结尾时 数组也就排序完成了
 * （默认设为升序排序）
 * 时间复杂度（最好）：数据有序的情况下 --- O（N）
 *         （最坏）：数据逆序的情况下 --- O（N^2)
 * 空间复杂度：O（1）
 * 稳定性：稳定（一个本身稳定的排序可以变成不稳定的；但是一个不稳定的排序不可以变成稳定的）
 * 特点：越有序，直接插入排序越快
 */
public class Insert_Sort {
    public static void insertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int j = i - 1;
            int tmp = array[i];
            for (; j >= 0 ; j--) {
                //如果比tmp大 就证明不是升序的 要往后挪动
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            /*当走到这一步有两种情况：1、j<0  （0 - i-1）的元素都遍历一遍了 要把tmp放到j+1的位置填充上
                                 2、j前面的元素都比tmp小了 要把tmp放回j+1的位置
            */
            array[j+1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {1,3,5,7,9,2,4,6,8};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }
}

